Appearance
Day 10:二维叉积、线段求交与共线重叠
学习方向:线性代数 + 计算机图形学 + CAD 开发
编程语言:TypeScript
核心主题:二维叉积、方向判断、平行与共线、参数方程、线段求交、重叠区间、退化线段
一、学习目标
本节在 Day 09 向量投影和点到线段距离的基础上,学习二维几何中另一个非常重要的算法:线段与线段的相交检测。
主要解决以下问题:
- 什么是二维叉积?
- 叉积与点积有什么区别?
- 如何利用叉积判断两个向量的方向关系?
- 如何判断两条直线是否平行?
- 如何判断两条直线是否共线?
- 如何使用参数方程表示线段?
- 如何推导两条直线的交点参数 t、u?
- 如何判断交点是否位于有限线段上?
- 如何处理共线线段的重叠?
- 如何处理线段端点接触?
- 如何处理零长度线段?
- 如何使用 TypeScript 实现完整的
intersectSegments()?
完成标准
- [ ] 理解二维叉积的计算公式。
- [ ] 能根据叉积正负判断方向。
- [ ] 能区分平行与共线。
- [ ] 理解线段参数方程。
- [ ] 能推导交点参数 t、u。
- [ ] 能计算两条线段的交点。
- [ ] 能判断交点是否位于有限线段内。
- [ ] 能计算共线线段的重叠区间。
- [ ] 能处理端点接触。
- [ ] 能处理零长度线段。
- [ ] 能实现
pointOnSegment()。 - [ ] 能实现
intersectCollinearSegments()。 - [ ] 能实现
intersectSegments()。
二、问题背景:CAD 为什么需要线段求交?
假设 CAD 中存在两条线段:
text
A ---------------- B
|
|
|
C
|
|
D两条线段存在一个交点。
CAD 需要计算:
- 是否相交?
- 交点坐标是多少?
- 交点是否位于两条有限线段内?
- 如果两条线段重叠,重叠部分是什么?
- 如果只是端点接触,应该返回什么?
- 如果某条线段长度为零,如何处理?
这些问题广泛应用于:
- CAD 交点吸附。
- 线段修剪(Trim)。
- 线段延长(Extend)。
- 图形碰撞检测。
- 多边形边界检测。
- 图形裁剪。
- 几何布尔运算。
- 施工图辅助绘制。
本节最终目标是实现:
typescript
function intersectSegments(
A: Vector2,
B: Vector2,
C: Vector2,
D: Vector2
): IntersectionResult三、回顾向量点积(Dot Product)
Day 04、Day 05 和 Day 09 已经学习点积。
已知:
点积:
几何公式:
点积主要用于:
- 计算夹角。
- 判断垂直。
- 计算投影。
- 计算最近点。
- 计算线段参数。
TypeScript
typescript
type Vector2 = {
x: number;
y: number;
};
function dotProduct(
a: Vector2,
b: Vector2
): number {
return a.x * b.x + a.y * b.y;
}四、二维叉积(Cross Product)
4.1 什么是叉积?
对于二维向量:
定义二维叉积:
与点积不同:
- 点积使用加法。
- 二维叉积使用减法。
- 两者在二维情况下都返回一个标量。
4.2 TypeScript 实现
typescript
function crossProduct(
a: Vector2,
b: Vector2
): number {
return a.x * b.y - a.y * b.x;
}4.3 计算示例
已知:
计算:
得到:
4.4 二维叉积与三维叉积的关系
严格来说,三维向量叉积的结果是向量。
将二维向量扩展到 XY 平面:
三维叉积:
二维叉积通常只保留 Z 分量:
所以二维叉积返回标量。
五、叉积的几何意义
5.1 叉积与方向
在 Y 轴向上的数学坐标系中:
| 叉积结果 | 几何意义 |
|---|---|
| 从 a 到 b 逆时针转动 | |
| 从 a 到 b 顺时针转动 | |
| 两个向量平行,或存在零向量 |
5.2 叉积为正
例如:
计算:
因此:
表示从 a 到 b 逆时针旋转 90°。
5.3 叉积为负
例如:
计算:
因此:
表示从 a 到 b 顺时针旋转 90°。
5.4 叉积为零
例如:
计算:
说明两个非零向量平行。
5.5 叉积与面积
二维叉积的绝对值等于两个向量构成的平行四边形面积:
例如:
得到:
由两个向量构成的三角形面积为:
这也是后续多边形面积计算的基础。
六、点积与叉积的区别
| 对比项目 | 点积 | 二维叉积 |
|---|---|---|
| 公式 | ||
| 返回值 | 标量 | 标量 |
| 三角函数关系 | ||
| 判断垂直 | 适合 | 不直接用于判断 |
| 判断平行 | 不直接用于判断 | 适合 |
| 计算投影 | 适合 | 不直接用于计算 |
| 判断方向 | 可判断夹角锐钝 | 可判断左右转向 |
| CAD 应用 | 拾取、距离、投影 | 相交、方向、共线 |
二维叉积还满足:
这里的
注意:
如果使用浏览器中 Y 轴向下的屏幕坐标,叉积正负对应的视觉旋转方向会发生变化。
七、使用叉积判断点在线段的哪一侧
已知三个点:
定义:
计算:
在 Y 轴向上的坐标系中:
- 大于 0:P 位于有向直线 AB 左侧。
- 小于 0:P 位于有向直线 AB 右侧。
- 等于 0:A、B、P 共线,或者 AB 退化为点。
TypeScript
typescript
function subtractVector(
a: Vector2,
b: Vector2
): Vector2 {
return {
x: a.x - b.x,
y: a.y - b.y
};
}
function orientation(
A: Vector2,
B: Vector2,
P: Vector2
): number {
const AB = subtractVector(B, A);
const AP = subtractVector(P, A);
return crossProduct(AB, AP);
}示例
typescript
const A = { x: 0, y: 0 };
const B = { x: 10, y: 0 };
console.log(
orientation(A, B, { x: 5, y: 5 })
);
// 50:左侧
console.log(
orientation(A, B, { x: 5, y: -5 })
);
// -50:右侧
console.log(
orientation(A, B, { x: 5, y: 0 })
);
// 0:共线注意:
共线不代表点一定在线段内部。
例如:
三个点共线,但 P 不在线段 AB 上。
八、判断两条直线是否平行
已知两条线段:
定义方向向量:
如果:
则两个方向向量线性相关。
当 r、s 都不是零向量时,说明两条直线平行。
TypeScript
typescript
function areParallel(
A: Vector2,
B: Vector2,
C: Vector2,
D: Vector2
): boolean {
const r = subtractVector(B, A);
const s = subtractVector(D, C);
const rr = dotProduct(r, r);
const ss = dotProduct(s, s);
if (rr === 0 || ss === 0) {
return false;
}
return crossProduct(r, s) === 0;
}这里约定:
零长度线段不参与普通直线的平行判断。
示例
typescript
const A = { x: 0, y: 0 };
const B = { x: 10, y: 0 };
const C = { x: 0, y: 5 };
const D = { x: 10, y: 5 };
console.log(
areParallel(A, B, C, D)
);
// true九、平行与共线的区别
这是 Day 10 的重点。
9.1 平行
两条直线方向相同或相反,但不一定在同一条直线上。
例如:
text
A ---------------- B
C ---------------- D9.2 共线
两条线段位于同一条无限直线上。
例如:
text
A -------- C -------- B -------- D9.3 共线判断公式
定义:
如果:
并且:
在 AB、CD 都不是零长度线段的前提下,说明两条直线共线。
9.4 TypeScript
typescript
function areCollinear(
A: Vector2,
B: Vector2,
C: Vector2,
D: Vector2
): boolean {
const r = subtractVector(B, A);
const s = subtractVector(D, C);
const q = subtractVector(C, A);
if (
dotProduct(r, r) === 0 ||
dotProduct(s, s) === 0
) {
return false;
}
return (
crossProduct(r, s) === 0 &&
crossProduct(q, r) === 0
);
}9.5 示例:平行但不共线
方向向量:
计算:
但:
因此:
两条直线平行,但不共线。
十、线段的参数方程
10.1 什么是参数方程?
已知线段:
线段所在直线上的任意点可以表示为:
其中:
10.2 参数 t 的几何意义
| t | 位置 |
|---|---|
| A 点外侧 | |
| A 点 | |
| AB 内部 | |
| B 点 | |
| B 点外侧 |
因此:
表示点位于有限线段 AB 上。
10.3 示例
已知:
参数方程:
当:
得到:
当:
得到:
此时点位于线段延长线上。
10.4 TypeScript
typescript
function pointAt(
A: Vector2,
B: Vector2,
t: number
): Vector2 {
return {
x: A.x + (B.x - A.x) * t,
y: A.y + (B.y - A.y) * t
};
}测试:
typescript
console.log(
pointAt(
{ x: 0, y: 0 },
{ x: 10, y: 10 },
0.5
)
);
// { x: 5, y: 5 }十一、两条直线的交点推导
这是 Day 10 最重要的公式推导。
11.1 定义两条直线
第一条:
第二条:
定义:
那么:
11.2 相交条件
如果两条直线相交,那么交点相同:
整理:
因此:
现在有两个未知数:
目标是求出它们。
11.3 推导 t
原方程:
两边与 s 做叉积:
根据叉积的分配律:
因为:
所以:
得到:
11.4 推导 u
原方程:
两边与 r 做叉积:
展开:
因为:
并且:
所以:
得到:
11.5 最终公式
前提:
也就是说,两条直线不能平行。
十二、判断两条有限线段是否相交
求出 t、u 后:
如果:
并且:
那么两条有限线段相交。
否则:
两条无限直线虽然可能相交,但交点不在两条有限线段的公共范围内。
TypeScript 判断
typescript
if (
t < 0 || t > 1 ||
u < 0 || u > 1
) {
return { type: "none" };
}如果满足范围:
typescript
const intersection = pointAt(A, B, t);即可得到交点。
十三、普通线段相交示例
已知:
第一步:计算方向向量
第二步:计算分母
分母不为零,因此两条直线不平行。
第三步:计算 t
所以:
第四步:计算 u
所以:
第五步:判断范围
两者均满足。
因此两条线段相交。
第六步:计算交点
得到:
十四、为什么不能只判断分母是否为零?
如果:
说明两条直线方向平行。
但是存在两种情况。
情况 1:平行但不共线
text
A ---------------- B
C ---------------- D结果:
typescript
{ type: "none" }情况 2:共线
text
A -------- C -------- B -------- D此时可能:
- 完全分离。
- 端点接触。
- 部分重叠。
- 完全包含。
- 完全重合。
因此:
分母为零时,不能直接返回不相交。
必须进一步判断是否共线。
十五、共线线段的重叠问题
15.1 示例
已知:
四个点位于同一条直线上。
排列关系:
text
A -------- C -------- B -------- D因此重叠部分为:
text
C -------- B即:
15.2 如何计算?
使用 Day 09 学习的向量投影。
将 C、D 投影到 AB 的参数轴上。
十六、共线线段的参数投影
16.1 定义向量
线段 AB 参数区间:
16.2 计算 C 的参数
16.3 计算 D 的参数
16.4 示例
已知:
首先:
计算:
计算:
因此:
线段 AB:
线段 CD:
它们的交集:
十七、计算重叠区间
17.1 为什么需要 min 和 max?
因为线段 CD 的端点顺序可能相反。
例如:
那么:
如果直接假设:
就可能得到错误结果。
因此需要先排序:
17.2 与 AB 区间求交
AB 的参数区间:
CD 的参数区间:
交集起点:
交集终点:
合并写法:
17.3 判断结果
| 条件 | 几何结果 |
|---|---|
| 不相交 | |
| 端点接触 | |
| 存在重叠线段 |
17.4 计算重叠端点
TypeScript:
typescript
const start = pointAt(A, B, startT);
const end = pointAt(A, B, endT);十八、设计线段求交返回类型
线段求交可能存在三种结果:
- 不相交。
- 相交于一个点。
- 重叠一段线段。
因此不应该只返回:
typescript
boolean更合理的方式是使用 TypeScript 联合类型。
18.1 IntersectionResult
typescript
type IntersectionResult =
| {
type: "none";
}
| {
type: "point";
point: Vector2;
}
| {
type: "overlap";
start: Vector2;
end: Vector2;
};18.2 不相交
typescript
{
type: "none"
}18.3 单点相交
typescript
{
type: "point",
point: {
x: 5,
y: 5
}
}18.4 线段重叠
typescript
{
type: "overlap",
start: {
x: 5,
y: 5
},
end: {
x: 10,
y: 10
}
}18.5 为什么使用联合类型?
因为不同相交情况需要不同的数据。
例如:
CAD 交点吸附:
typescript
if (result.type === "point") {
// 使用 result.point
}CAD 重叠检测:
typescript
if (result.type === "overlap") {
// 使用 result.start 和 result.end
}TypeScript 可以根据 type 自动缩小类型范围。
十九、实现 intersectCollinearSegments()
19.1 函数职责
专门处理两条已经确认共线的非零长度线段。
需要:
- 计算 AB 的方向向量。
- 计算 C、D 在 AB 上的参数。
- 计算两个参数区间的交集。
- 判断是否分离。
- 判断是否端点接触。
- 返回重叠线段。
19.2 TypeScript 完整实现
typescript
function intersectCollinearSegments(
A: Vector2,
B: Vector2,
C: Vector2,
D: Vector2
): IntersectionResult {
// 1. 计算方向向量
const r = subtractVector(B, A);
const q = subtractVector(C, A);
// 2. AB 长度平方
const rr = dotProduct(r, r);
// 3. 防止零长度线段
if (rr === 0) {
return { type: "none" };
}
// 4. 确保 C 位于 AB 所在直线上
if (crossProduct(q, r) !== 0) {
return { type: "none" };
}
// 5. C 在 AB 参数轴上的位置
const t0 = dotProduct(q, r) / rr;
// 6. D 在 AB 参数轴上的位置
const t1 = dotProduct(
subtractVector(D, A),
r
) / rr;
// 7. 求区间交集
const startT = Math.max(
0,
Math.min(t0, t1)
);
const endT = Math.min(
1,
Math.max(t0, t1)
);
// 8. 不相交
if (startT > endT) {
return { type: "none" };
}
// 9. 只有一个公共点
if (startT === endT) {
return {
type: "point",
point: pointAt(A, B, startT)
};
}
// 10. 存在重叠线段
return {
type: "overlap",
start: pointAt(A, B, startT),
end: pointAt(A, B, endT)
};
}19.3 示例:部分重叠
typescript
const result = intersectCollinearSegments(
{ x: 0, y: 0 },
{ x: 10, y: 10 },
{ x: 5, y: 5 },
{ x: 15, y: 15 }
);
console.log(result);预期:
typescript
{
type: "overlap",
start: { x: 5, y: 5 },
end: { x: 10, y: 10 }
}19.4 示例:完全分离
typescript
const result = intersectCollinearSegments(
{ x: 0, y: 0 },
{ x: 5, y: 5 },
{ x: 8, y: 8 },
{ x: 12, y: 12 }
);预期:
typescript
{
type: "none"
}19.5 示例:端点接触
typescript
const result = intersectCollinearSegments(
{ x: 0, y: 0 },
{ x: 5, y: 5 },
{ x: 5, y: 5 },
{ x: 10, y: 10 }
);预期:
typescript
{
type: "point",
point: { x: 5, y: 5 }
}二十、零长度线段问题
20.1 什么是零长度线段?
如果:
那么:
因此:
线段退化为一个点。
20.2 为什么必须特殊处理?
普通求交公式:
如果 r 是零向量:
但这并不能说明两条线段正常平行或共线。
同时,共线投影公式:
也会出现除零问题。
20.3 需要处理的情况
| AB | CD | 处理方式 |
|---|---|---|
| 正常线段 | 正常线段 | 普通求交 |
| 零长度 | 正常线段 | 判断 A 是否在 CD 上 |
| 正常线段 | 零长度 | 判断 C 是否在 AB 上 |
| 零长度 | 零长度 | 判断 A、C 是否重合 |
二十一、实现 pointOnSegment()
21.1 函数目标
判断点 P 是否位于有限线段 AB 上。
需要满足:
- P 与 AB 共线。
- P 位于 A、B 之间。
- 正确处理 A=B 的情况。
21.2 数学原理
定义:
首先判断共线:
然后计算参数:
最后判断:
21.3 TypeScript 实现
typescript
function pointOnSegment(
P: Vector2,
A: Vector2,
B: Vector2
): boolean {
const r = subtractVector(B, A);
const q = subtractVector(P, A);
const rr = dotProduct(r, r);
// AB 退化为点
if (rr === 0) {
return (
P.x === A.x &&
P.y === A.y
);
}
// 判断是否共线
if (crossProduct(r, q) !== 0) {
return false;
}
// 计算投影参数
const t = dotProduct(q, r) / rr;
// 判断是否在线段范围内
return t >= 0 && t <= 1;
}21.4 测试
typescript
const A = { x: 0, y: 0 };
const B = { x: 10, y: 0 };
console.log(
pointOnSegment(
{ x: 5, y: 0 },
A,
B
)
);
// truetypescript
console.log(
pointOnSegment(
{ x: 15, y: 0 },
A,
B
)
);
// falsetypescript
console.log(
pointOnSegment(
{ x: 5, y: 3 },
A,
B
)
);
// false二十二、实现完整 intersectSegments()
22.1 算法整体流程
text
输入 A、B、C、D
|
v
计算 r、s、q
|
v
计算 rr、ss
|
v
判断零长度线段
|
+---- 两条都是点
| |
| v
| 判断是否重合
|
+---- AB 是点
| |
| v
| pointOnSegment(A,C,D)
|
+---- CD 是点
| |
| v
| pointOnSegment(C,A,B)
|
v
计算 denominator = cross(r,s)
|
v
判断 denominator 是否为 0
|
+---- 是
| |
| v
| 判断是否共线
| |
| +---- 否:none
| |
| +---- 是:共线区间求交
|
+---- 否
|
v
计算 t、u
|
v
判断 [0,1]
|
+---- 不满足:none
|
+---- 满足:point22.2 TypeScript 完整实现
typescript
function intersectSegments(
A: Vector2,
B: Vector2,
C: Vector2,
D: Vector2
): IntersectionResult {
// 1. 计算方向向量
const r = subtractVector(B, A);
const s = subtractVector(D, C);
const q = subtractVector(C, A);
// 2. 计算长度平方
const rr = dotProduct(r, r);
const ss = dotProduct(s, s);
// 3. 两条线段都退化为点
if (rr === 0 && ss === 0) {
if (
A.x === C.x &&
A.y === C.y
) {
return {
type: "point",
point: A
};
}
return { type: "none" };
}
// 4. AB 退化为点
if (rr === 0) {
return pointOnSegment(A, C, D)
? {
type: "point",
point: A
}
: {
type: "none"
};
}
// 5. CD 退化为点
if (ss === 0) {
return pointOnSegment(C, A, B)
? {
type: "point",
point: C
}
: {
type: "none"
};
}
// 6. 计算叉积
const denominator = crossProduct(r, s);
// 7. 平行情况
if (denominator === 0) {
// 平行但不共线
if (crossProduct(q, r) !== 0) {
return { type: "none" };
}
// 共线线段求交
return intersectCollinearSegments(
A,
B,
C,
D
);
}
// 8. 非平行:计算交点参数
const t = crossProduct(q, s) / denominator;
const u = crossProduct(q, r) / denominator;
// 9. 判断交点是否位于有限线段
if (
t < 0 || t > 1 ||
u < 0 || u > 1
) {
return { type: "none" };
}
// 10. 计算交点
return {
type: "point",
point: pointAt(A, B, t)
};
}二十三、完整测试用例
测试 1:普通交叉
typescript
intersectSegments(
{ x: 0, y: 0 },
{ x: 10, y: 10 },
{ x: 0, y: 10 },
{ x: 10, y: 0 }
);预期:
typescript
{
type: "point",
point: { x: 5, y: 5 }
}测试 2:平行不相交
typescript
intersectSegments(
{ x: 0, y: 0 },
{ x: 10, y: 0 },
{ x: 5, y: 5 },
{ x: 15, y: 5 }
);预期:
typescript
{ type: "none" }测试 3:共线部分重叠
typescript
intersectSegments(
{ x: 0, y: 0 },
{ x: 10, y: 10 },
{ x: 5, y: 5 },
{ x: 15, y: 15 }
);预期:
typescript
{
type: "overlap",
start: { x: 5, y: 5 },
end: { x: 10, y: 10 }
}测试 4:共线完全分离
typescript
intersectSegments(
{ x: 0, y: 0 },
{ x: 5, y: 5 },
{ x: 8, y: 8 },
{ x: 12, y: 12 }
);预期:
typescript
{ type: "none" }测试 5:端点接触
typescript
intersectSegments(
{ x: 0, y: 0 },
{ x: 5, y: 5 },
{ x: 5, y: 5 },
{ x: 10, y: 10 }
);预期:
typescript
{
type: "point",
point: { x: 5, y: 5 }
}测试 6:反向重叠
typescript
intersectSegments(
{ x: 0, y: 0 },
{ x: 10, y: 0 },
{ x: 8, y: 0 },
{ x: 2, y: 0 }
);预期:
typescript
{
type: "overlap",
start: { x: 2, y: 0 },
end: { x: 8, y: 0 }
}测试 7:AB 退化为点且在线段上
typescript
intersectSegments(
{ x: 5, y: 5 },
{ x: 5, y: 5 },
{ x: 0, y: 0 },
{ x: 10, y: 10 }
);预期:
typescript
{
type: "point",
point: { x: 5, y: 5 }
}测试 8:CD 退化为点且不在线段上
typescript
intersectSegments(
{ x: 0, y: 0 },
{ x: 10, y: 0 },
{ x: 5, y: 5 },
{ x: 5, y: 5 }
);预期:
typescript
{ type: "none" }测试 9:两个相同的点
typescript
intersectSegments(
{ x: 5, y: 5 },
{ x: 5, y: 5 },
{ x: 5, y: 5 },
{ x: 5, y: 5 }
);预期:
typescript
{
type: "point",
point: { x: 5, y: 5 }
}测试 10:两个不同的点
typescript
intersectSegments(
{ x: 5, y: 5 },
{ x: 5, y: 5 },
{ x: 6, y: 5 },
{ x: 6, y: 5 }
);预期:
typescript
{ type: "none" }二十四、CAD 实际应用场景
24.1 交点吸附(Intersection Snap)
当鼠标靠近两条线段交点时:
- 获取候选线段。
- 调用
intersectSegments()。 - 判断返回类型。
- 获取交点坐标。
- 计算交点与鼠标的屏幕距离。
- 如果距离小于吸附容差,则显示吸附标记。
24.2 线段修剪(Trim)
例如:
text
A ---------------- B
|
|
C
|
D如果需要以 CD 为边界修剪 AB:
- 计算 AB 与 CD 所在直线或线段的交点。
- 判断交点是否满足修剪工具的规则。
- 根据鼠标选择的保留侧,更新 AB 的端点。
注意:
完整 Trim 工具可能需要直线延长、边界选择和多候选交点处理,不能仅依赖有限线段求交。
24.3 线段延长(Extend)
Extend 通常需要计算:
- 线段所在直线与目标边界的交点。
- 交点是否位于允许的延长方向。
- 哪个端点需要延长。
24.4 多边形边界检测
多边形由多个线段组成。
判断两条多边形边界是否相交时,可以逐对检测边。
24.5 图形布尔运算
例如:
- Union(并集)。
- Intersection(交集)。
- Difference(差集)。
线段求交是二维布尔运算的重要基础。
但完整布尔运算还需要:
- 多边形拓扑关系。
- 交点排序。
- 边界分割。
- 内外关系判断。
- 数值稳健性处理。
二十五、Day 10 常见错误
错误 1:叉积为零就认为不相交
错误:
typescript
if (denominator === 0) {
return { type: "none" };
}因为两条线段可能共线并重叠。
正确做法:
继续判断是否共线。
错误 2:平行等于共线
错误。
需要判断:
以及:
错误 3:共线等于重叠
错误。
共线线段可能完全分离。
需要进一步计算参数区间交集。
错误 4:只判断 t,不判断 u
错误。
交点必须同时位于两条有限线段上。
因此:
并且:
错误 5:没有处理反向线段
例如:
如果默认:
可能得到错误的重叠区间。
正确做法:
typescript
Math.min(t0, t1)
Math.max(t0, t1)错误 6:忽略零长度线段
如果:
那么:
普通求交公式可能失效。
必须先处理退化情况。
错误 7:浮点数直接比较
例如:
typescript
denominator === 0对于整数坐标和简单测试数据通常容易理解。
但在实际 CAD 中,浮点计算可能存在误差。
例如理论上应该为零的叉积,计算结果可能是:
typescript
1.4210854715202004e-14不过,不能简单地将所有比较替换为:
typescript
Math.abs(cross) < 1e-10因为叉积的量纲是长度平方,结果会受到坐标尺度影响。
后续工程实践中,需要学习:
- 相对容差。
- 尺度相关容差。
- 稳健方向谓词。
- 近似共线与精确共线的区别。
- 浮点数误差传播。
二十六、Day 10 练习题
练习 1:二维叉积
已知:
求:
并判断从 a 到 b 的旋转方向。
练习 2:平行判断
已知:
判断两条直线是否平行。
练习 3:共线判断
已知:
判断:
- 是否平行?
- 是否共线?
- 是否重叠?
练习 4:普通线段求交
已知:
求:
- r。
- s。
- q。
- 分母
。 - 参数 t。
- 参数 u。
- 交点坐标。
练习 5:共线重叠
已知:
求:
- t0。
- t1。
- startT。
- endT。
- 重叠线段端点。
练习 6:反向线段
已知:
求重叠区间。
练习 7:零长度线段
已知:
判断两条线段是否相交。
练习 8:TypeScript 综合题
独立实现:
typescript
function intersectSegments(
A: Vector2,
B: Vector2,
C: Vector2,
D: Vector2
): IntersectionResult {
// TODO
}要求:
- 普通相交。
- 平行不相交。
- 共线重叠。
- 共线分离。
- 端点接触。
- 反向重叠。
- 零长度线段。
- 两个点重合。
- 两个点不重合。
二十七、Day 10 核心公式汇总
| 知识点 | 核心公式 |
|---|---|
| 向量减法 | |
| 点积 | |
| 二维叉积 | |
| 叉积与夹角 | $a\times b= |
| 平行判断 | |
| 共线判断 | |
| 参数方程 | |
| 交点参数 t | |
| 交点参数 u | |
| 有限线段判断 | |
| 交点坐标 | |
| 共线投影 t0 | |
| 共线投影 t1 | |
| 重叠起点 | |
| 重叠终点 |
二十八、Day 10 最终验收清单
数学基础
- [ ] 理解二维叉积。
- [ ] 能手算二维叉积。
- [ ] 能根据叉积判断方向。
- [ ] 理解叉积与面积的关系。
- [ ] 能判断两条直线是否平行。
- [ ] 能判断两条直线是否共线。
- [ ] 理解线段参数方程。
- [ ] 能推导交点参数 t、u。
- [ ] 能判断交点是否位于有限线段内。
- [ ] 能计算共线线段的重叠区间。
TypeScript
- [ ] 实现
crossProduct()。 - [ ] 实现
orientation()。 - [ ] 实现
areParallel()。 - [ ] 实现
areCollinear()。 - [ ] 实现
pointAt()。 - [ ] 实现
pointOnSegment()。 - [ ] 实现
intersectCollinearSegments()。 - [ ] 实现
intersectSegments()。 - [ ] 能通过全部测试用例。
CAD 应用
- [ ] 能计算两条线段的交点。
- [ ] 能实现基础交点吸附。
- [ ] 理解线段修剪的几何基础。
- [ ] 理解线段延长的几何基础。
- [ ] 能判断共线线段是否重叠。
- [ ] 能处理端点接触。
- [ ] 能处理零长度线段。
- [ ] 理解线段求交与多边形算法的关系。
- [ ] 理解浮点误差对几何计算的影响。
二十九、Day 10 知识总结
本节最重要的三个知识点:
1. 叉积可以判断方向、平行和共线
二维叉积是计算几何中非常重要的基础工具。
2. 参数方程可以将几何求交转换为代数问题
两条直线:
相交时:
通过叉积得到:
然后判断:
即可确定有限线段是否相交。
3. 共线重叠可以转换为一维区间求交
将 CD 的两个端点投影到 AB 的参数轴上:
然后计算:
根据 startT 和 endT 的大小关系,判断:
- 不相交。
- 单点接触。
- 线段重叠。
三十、Day 06–Day 10 阶段知识联系
text
Day 06:矩阵基础
|
├── 矩阵结构
├── 矩阵乘法
└── 单位矩阵
|
v
Day 07:二维仿射变换
|
├── 缩放
├── 旋转
├── 平移
├── 齐次坐标
└── 组合变换
|
v
Day 08:逆矩阵与坐标转换
|
├── 行列式
├── 逆矩阵
├── worldToScreen
└── screenToWorld
|
v
Day 09:点到线段距离
|
├── 向量投影
├── Clamp
├── 最近点
├── 最短距离
└── hitTestSegment
|
v
Day 10:线段求交
|
├── 二维叉积
├── 平行判断
├── 共线判断
├── 参数方程
├── 交点计算
├── 重叠区间
└── 零长度线段五天的核心数学工具
| 数学工具 | 主要作用 | CAD 应用 |
|---|---|---|
| 矩阵 | 坐标变换 | 平移、旋转、缩放 |
| 逆矩阵 | 撤销坐标变换 | 屏幕转世界坐标 |
| 点积 | 投影与距离 | 拾取、最近点吸附 |
| 叉积 | 方向与相交关系 | 交点吸附、线段求交 |
| 参数方程 | 表示线段上的位置 | 求交、裁剪、修剪 |
| 区间求交 | 计算重叠范围 | 共线重叠检测 |
Day 10 核心结论:
点积主要解决投影与距离问题。
叉积主要解决方向、平行、共线和相交问题。
参数方程将二维几何问题转换为代数问题。
通过叉积、点积、参数方程和区间求交,可以实现一个能够处理普通相交、共线重叠、端点接触和零长度线段的二维线段求交算法。
当前学习进度:Day 10 完成。
Day 06–Day 10 阶段复习整理完成。
下一阶段:Day 11——点与多边形的位置关系(Point in Polygon)。